﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode100Hot.链表
{
    internal class _148
    {

        static void Main148(string[] args)
        {//4213
            //使用尾插法建立一个链表
            int[] nums = { 4, 2, 1, 3 };


            ListNode root = new ListNode(nums[0]);
            ListNode pre = root;

            for (int i = 1; i < nums.Length; i++)
            {
                ListNode newNode = new ListNode(nums[i]);
                pre.next = newNode;
                pre = newNode;

            }

            ListNode curNode = root;
            while (curNode != null)
            {
                Console.WriteLine(curNode.val);
                curNode = curNode.next;
            }
            Sol148 sol = new Sol148();
            ListNode result = sol.SortList(root);
            while (result != null)
            {
                Console.WriteLine("mysort:" + result.val);
                result = result.next;
            }
            //ListNodeLemon head = new ListNodeLemon(-1);
            //ListNodeLemon cur = head;





            //for (int j = 0; j < nums.Length; j++)
            //{

            //    //ans加入链表
            //    cur.next = new ListNodeLemon(nums[j]);
            //    cur = cur.next;


            //}
            //SolLemon3 solLemon3 = new SolLemon3();
            //ListNodeLemon res = solLemon3.ListSort(head.next);

            //while (res != null)
            //{
            //    Console.WriteLine("lemonsort:" + res.val);
            //    res = res.next;
            //}
        }
    }


    class Sol148
    {


        public ListNode SortList2(ListNode head)
        {
            //冒泡排序，时间复杂度太高超时

            if (head == null || head.next == null)
            {
                return head;

            }

            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;


            bool flag = true;
            while (flag)
            {
                flag = false;

                ListNode pre = dummyHead;
                //ListNode cur = head;//这个赋值失败的原因是，head指向的节点是有可能发生交换的，所有应该用的是 dummyHead.next
                ListNode cur = pre.next;
                ListNode next = cur.next;
                while (next != null)
                {

                    if (cur.val > next.val)
                    {
                        //交换一下
                        flag = true;
                        cur.next = next.next;
                        next.next = cur;
                        pre.next = next;

                        pre = next;
                        //cur = pre.next;
                        next = cur.next;
                    }
                    else
                    {
                        pre = cur;
                        cur = next;
                        next = next.next;


                    }
                }



            }


            return dummyHead.next;
        }
        public ListNode SortList(ListNode head)//归并排序

        {
            //只有一个元素就直接返回
            if(head==null|| head.next == null)
            {
                return head;
            }


            ListNode fast = head;
            ListNode low = head;
            ListNode pre = low;
            while ( fast != null && fast.next != null) { 
            
            
            fast= fast.next.next;
                pre = low;
                low=low.next;
            }

            //low在链表中间位置
            //但是head和low没有断开，
            pre.next = null;

            ListNode left = SortList(head);//前面
          
            ListNode right = SortList(low);//后面

            //合并left，right
           return  MerageList(left, right);    





        }

        private ListNode MerageList(ListNode left, ListNode right)//合并两个有序链表
        {

            ListNode dummyHead = new ListNode(-1);
            ListNode Head = dummyHead;
            while (left!= null&&right!=null)
            {
                if (left.val > right.val)
                {

                    Head.next = right;
                    right = right.next;
                    Head = Head.next;

                }
                else
                {
                    Head.next = left;
                    left = left.next;
                    Head = Head.next;
                }

            }

            //有一个走完，全部接到后面

            if (left == null) {
                //接right
                Head.next = right;

            }
            else
            {
                Head.next = left;
            }

            return dummyHead.next;
        }
    }
}
